数学基础#

幂#

幂：幂是一个汉字词语，（汉语拼音：mì，注音：ㄇㄧˋ，音同“觅”），意思是指乘方运算的结果。指将自乘次。把看作乘方的结果，叫做“n的m次幂”或“n的m次方”。

$n^m$ : 指将n自乘m次，其中，n称为“底数”，m称为“指数”，叫做“n的m次幂”或“n的m次方”

运算规则编辑#

• 同底数幂相乘，底数不变，指数相加。 $a^n\times a^m =a^{n+m}$
• 同底数幂相除，底数不变，指数相减。 $a^n\div a^m =a^{n-m}$
• 幂的乘方，底数不变，指数相乘。 $(a^n)^m = a^{n\times m}$
• 同指数幂相乘，指数不变，底数相乘。 $a^n\times b^n=(a\times b)^n$
• 同指数幂相除，指数不变，底数相除。 $a^n\div b^n=(a\div b)^n$

有理数指数幂#

• 零指数幂 $a^0=1 \quad (a\neq 0)$
• 负指数幂 $a^{-n}=\frac{1}{a^n} \quad (a \neq 0)$
• 分数指数幂 $a^{\frac{n}{m}}=(a^n)^{\frac1m}=\sqrt[m]{a^n}$

对数#

对数：对数运算是幂运算的逆运算

$N = a^x (a>0, a\ne1)$, $x$就是$a$为底$N$的对数，记作$x=\log_a N$,其中：

• $a$ : 底
• $N$ : 真数
• $x$ : 以$a$为底$N$的对数

log 指的都是 $\log_2$

$\log 8$ = $\log_2 8$ = 3 ($2^3 = 8$)

1. 以10为底的对数称为常用对数,记为$\lg$，$\log_{10} =\lg$, $\log_2=\log$
2. 以无理数$e$($e=2.71828…$)为底的对数称为自然对数，记为$\ln$
3. 零没有对数
4. 实数范围内，负数没有对数；复数范围内，负数有对数

二分查找#

二分查找是对半查找，仅当列表有序时有效。

n个元素的列表，二分查找最多需要$log_2 n$ 步，简单顺序查找最多需要n步。

时间复杂度#

简单顺序查找的实践复杂度 $O(n)$

二分查找的时间复杂度 $O( \log n)$

时间复杂度表示了最糟糕情况下的运行时间

常用时间复杂度#

• $O(\log n)$ 对数时间
• $O(n)$ 线性时间
• $O(n \times \log n)$
• $O(n^2)$
• $O(n!)$ n的阶乘